public class _1092 {
    static class Solution1 {
        public String shortestCommonSupersequence(String str1, String str2) {
            //先找出公共最长子串
            int[][] dp = new int[str1.length() + 1][str2.length() + 1];
            for (int i = 1; i <= str1.length(); i++) {
                for (int j = 1; j <= str2.length(); j++) {
                    if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                        dp[i][j] = 1 + dp[i - 1][j - 1];
                    } else {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                    }
                }
            }
            //根据dp数组，来判断哪些字符在子串中，哪些不在
            StringBuilder res = new StringBuilder();
            int i = str1.length() - 1;
            int j = str2.length() - 1;
            while (i >= 0 || j >= 0) {
                if (i < 0) {
                    res.append(str2.charAt(j--));
                    continue;
                }
                if (j < 0) {
                    res.append(str1.charAt(i--));
                    continue;
                }
                int val = dp[i + 1][j + 1];
                //说明str1该位置的字符删除也不影响子串，所以要加入结果
                if (val == dp[i][j + 1]) {
                    res.append(str1.charAt(i--));
                } else if (val == dp[i + 1][j]) {
                    res.append(str2.charAt(j--));
                } else {
                    //为子串的字符，只需要添加一次
                    res.append(str2.charAt(j));
                    i--;
                    j--;
                }
            }
            return res.reverse().toString();
        }
    }
}
